package com.hjr.leetcode.question100;

import com.hjr.leetcode.util.entity.ListNode;

import java.util.ArrayList;

/**
 *19. 删除链表的倒数第 N 个结点
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 */
public class q19 {

    public static void main(String[] args) {
        ListNode listNode = removeNthFromEndP(new ListNode(1), 1);
        while (listNode != null){
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }

    //如何确定倒数第n个节点 1、遍历链表，得到链表的长度
    // 1ms 40mb
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        //预节点
        ListNode pre = new ListNode(0, head);
        ArrayList<ListNode> listNodes = new ArrayList<>();
        while (head != null){
            listNodes.add(head);
            head = head.next;
        }
        //节点位置不同，删除方式不同
        //1、在链表中间元素
        //2、在链表头
        //3、在链表尾
        if (listNodes.size() - n == 0){
            pre.next = pre.next.next;
        }else if (listNodes.size() - n == listNodes.size() - 1){
            listNodes.get(listNodes.size() - n - 1).next = null;
        }else {
            ListNode listNode1 = listNodes.get(listNodes.size() - n - 1);
            ListNode listNode2 = listNodes.get(listNodes.size() - n + 1);
            listNode1.next = listNode2;
        }
        return pre.next;
    }

    //如何确定倒数第n个节点 2、快慢指针
    // 0ms 40mb
    public static ListNode removeNthFromEndP(ListNode head, int n) {
        //预节点
        ListNode pre = new ListNode(0, head);
        ListNode slow = head, fast = head;
        //将fast移动到最后节点，计算长度，长度n也就是slow要移动到删除节点的次数
        int length = 1;
        while (fast != null && fast.next != null){
            fast = fast.next;
            length++;
        }

        if (length == n){
            //头节点
            if (length > 1){
                pre = pre.next;
            }else {
                pre.next = null;
            }
        }else if (length - n == 0){
            //尾节点
            fast = null;
        }else {
            for (int i = 0; i < length - n - 1; i++) {
                slow = slow.next;
            }
            slow.next = slow.next.next;
        }
        return pre.next;
    }
}
